//
// Created by Administrator on 2021/5/31.
//

/*
给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。

「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。*/
#include <iostream>
#include <climits>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
private:
    int num = 0;
public:
    int goodNodes(TreeNode *root) {
        dfs(root, INT_MIN);
        return this->num;
    }

    void dfs(TreeNode *root, int curMax) { // 保存从根节点到当前节点的最大值
        if (root == nullptr) return;
        curMax = max(curMax, root->val);
        if (root->val >= curMax) ++this->num;
        dfs(root->left, curMax);
        dfs(root->right, curMax);
    }
};

int main() {
    auto n1 = TreeNode(3),n2 = TreeNode(1),n3 = TreeNode(4),n4 = TreeNode(3),
    n5 = TreeNode(1),n6 = TreeNode(5);
    n1.left = &n2;
    n2.right = &n3;
    n2.left = &n4;
    n3.left = &n5;
    n3.right = &n6;
    Solution sol;
    cout << sol.goodNodes(&n1)<<endl;
    return 0;
}